/**
 *	在ASCII码中吗，每个字符都可以用一个数字代替，那么一个字符串同样可以转换为
 *	一个数字，通过一个函数将一个字符串转换为合适大小的数字，这个函数成为哈希函
 *	数，而这个数字就是存储这条字符串的数组的下标，下一次再遇到此字符串时，利用
 *	哈希函数可得到相同的数字，查找这个数字下标的数组元素就可以找到之前存储的字 
 *	符串，这就是散列查找，也称哈希查找。哈希查找的时间复杂度为O(1)，因为只需要
 *	利用哈希函数得到数组下标就可以通过该下标查找到元素
 *	但是哈希查找也有缺陷，易出现冲突，即两个不相同的字符串可能通过哈希函数得到
 *	的数字相同，尤其是数组规模不大时，这种冲突极易出现，解决冲突的方式有多种，
 *	此书采用的是链表法，即数组的每个元素是一个指向链表的指针，在链表中存放字符
 *	串，当遇到冲突字符串时，将冲突字符串添加到链表中，查找时遍历整个链表，寻找
 *	是否有相同字符串
**/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h> 
#include "./../6_5_quotestruct/getch/getch.h"

#define HASHSIZE 101
#define BUFSIZE  100

char buf[BUFSIZE];
int bufp = 0;

struct nlist 		// table entry
{
	struct nlist *next;	// next entry in chain
	char *name;		// define name
	char *defn;		// replacement text
};

static struct nlist *hashtab[HASHSIZE];		// pointer table


unsigned hash(char *s);
struct nlist *lookup(char *s);
struct nlist *install(char *name, char *defn);
int undef(char *name);
//char *strdup(char *s);
int getword(char *word, int lim);
int getch(void);
void ungetch(int c);

int main(void)
{
	char name[100], define[100];
	struct nlist *np;

	printf("请输入创建表的名字：\n");
	while(getword(name, 100) != EOF)
	{
		printf("请输入该名字的替换文本：\n");
		getword(define, 100);
		if(install(name, define) == NULL)
			break;
		printf("继续输入名字：\n");
	}

	printf("请输入待查找的名字：\n");
	while(getword(name, 100) != EOF)
	{
		if((np = lookup(name)) != NULL)
			printf("%s %s\n", np->name, np->defn);
		else
			printf("error\n");
	}

	printf("请输入待删除的名称：\n");
	while(getword(name, 100) != EOF)
	{
		if(undef(name))
			printf("删除成功\n");
		else
			printf("error\n");
	}

	printf("请输入待查找的名字：\n");
	while(getword(name, 100) != EOF)
	{
		if((np = lookup(name)) != NULL)
			printf("%s %s\n", np->name, np->defn);
		else
			printf("error\n");
	}
	return 0;
}

// hash: form hash value for string s
unsigned hash (char *s)
{
	unsigned hashval;

	for(hashval = 0; *s != '\0'; s++)
		hashval = *s + 31 * hashval;
	return hashval % HASHSIZE;
}

// lookup: look for s in hashtab
struct nlist *lookup(char *s)
{
	struct nlist *np;
	
	for(np = hashtab[hash(s)]; np != NULL; np = np->next)
		if(strcmp(s, np->name) == 0)
			return np;		// found
	return NULL;				// not found
}

// install: put (name, defn) in hashtab
struct nlist *install(char *name, char *defn)
{
	struct nlist *np;
	unsigned hashval;

	if((np = lookup(name)) == NULL)		// 查找链表有无匹配的名字，如果没有
	{
		np = (struct nlist *) malloc(sizeof(*np));
		if(np == NULL || (np->name = strdup(name)) == NULL)
			return NULL;
		hashval = hash(name);
		np->next = hashtab[hashval]; 	// 从链表的表头添加项，hashtab[hashval] 指向的是原链表的表头
		hashtab[hashval] = np;		// np 现在成为新的链表的表头，hashtab[hashval] 指向 np
	}
	else					// already there
		free((void *)np->defn);		// 释放原替换文本分配的空间
	if((np->defn = strdup(defn)) == NULL)	// 不管链表有无匹配的名字，都将通过此语句为 defn 分配空间并赋值
		return NULL;
	return np;
	
}

int undef(char *name)
{
	struct nlist *np1, *np2;

	for(np1 = hashtab[hash(name)], np2 = NULL; np1 != NULL; np2 = np1, np1 = np1->next)
	{
		if(!strcmp(name, np1->name))
		{
			if(np2 == NULL)
				hashtab[hash(name)] = np1->next;
			else
				np2->next = np1->next;
			free(np1->name);
			free(np1->defn);
			free(np1);
			np1 = NULL;
			return 1;
		}
	}
	return 0;
}
